package jjn.round2;

import commons.TreeNode;

/**
 * @author Jiang Jining
 * @since 2023-05-22 22:17
 */
public class LeetCode1080_InsufficientNodes {
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        return hasSufficientNode(root, 0, limit) ? root : null;
    }
    
    private boolean hasSufficientNode(TreeNode node, int sum, int limit) {
        if (node == null) {
            return false;
        }
        if (node.left == null && node.right == null) {
            return sum + node.val >= limit;
        }
        boolean leftHasEfficient = hasSufficientNode(node.left, sum + node.val, limit);
        boolean rightHasEfficient = hasSufficientNode(node.right, sum + node.val, limit);
        if (!leftHasEfficient) {
            node.left = null;
        }
        if (!rightHasEfficient) {
            node.right = null;
        }
        return leftHasEfficient || rightHasEfficient;
    }
}
